#pragma once
#include <iostream>
#include <queue>
#include <vector>


template<class T>
struct HuffmanTreeNode {
	HuffmanTreeNode<T>* _left;
	HuffmanTreeNode<T>* _right;
	T _weight;

	HuffmanTreeNode(const T& weight = T())
		:_left(nullptr)
		, _right(nullptr)
		, _weight(weight)
	{}
};


template<class T>
class HuffmanTree {
	typedef HuffmanTreeNode<T> Node;
	class Compare {
	public:
		bool operator()(const Node* left, const Node* right) {
			return left->_weight > right->_weight;
		}
	};
public:
	HuffmanTree()
		:_root(nullptr)
	{}

	HuffmanTree(const std::vector<T>& vw, const T& invalid) {
		std::priority_queue < Node*, std::vector<Node*>, Compare> q;
		for (auto& i : vw) {
			if (invalid == i) continue;
			q.push(new Node(i));
		}

		while (q.size() > 1) {
			Node* left = q.top();
			q.pop();

			Node* right = q.top();
			q.pop();

			Node* parent = new Node(left->_weight + right->_weight);
			parent->_left = left;
			parent->_right = right;

			q.push(parent);
		}

		_root = q.top();
	}

	Node* GetRoot() {
		return _root;
	}

	~HuffmanTree() {
		Destory(_root);
	}

private:
	void Destory(Node* root) {
		if (root) {
			Destory(root->_left);
			Destory(root->_right);
			delete root;
			root = nullptr;
		}
	}

private:
	Node* _root;
};

